package no34;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.List;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/22 10:41
 * II 二叉树中和为某一值的路径
 * https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
 */
public class Solution {

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        pathSumDFS(root, target, new ArrayList<>(), ret);
        return ret;
    }

    // 深度优先搜索
    private void pathSumDFS(TreeNode root, int target, List<Integer> curRes, List<List<Integer>> res) {
        if (root == null) {
            return;
        }
        curRes.add(root.val); // 记录当前路径值
        target -= root.val;
        // 判断是否达到目标值, 记录结果
        if (root.left == null && root.right == null && target == 0) {
            res.add(new ArrayList<>(curRes));
        }
        // 继续左右子树深搜
        pathSumDFS(root.left, target, curRes, res);
        pathSumDFS(root.right, target, curRes, res);
        // 回溯
        curRes.remove(curRes.size()-1);
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
